import com.sun.scenario.effect.impl.sw.java.JSWColorAdjustPeer;

public class MySort {
    public static void qhzz(int[] array){
       qh(array , 0 , array.length-1);
    }
    private static void qh(int[] array , int left , int right){
        if(left >= right) {
            return;
        }
        int pivot = partition(array , left , right) ;
        qh(array , left , pivot-1);
        qh(array , pivot+1 , right) ;
    }

    private static int partition(int[] array , int left , int right){

        int cur = left + 1 ;
        int prev = left ;
        while(cur <= right){
            if(array[left] > array[cur] && (++prev)!=cur){
                swap(array , prev , cur);
            }
            cur ++ ;
        }
        swap(array , left , prev);
       return prev ;
    }
    private static void swap(int[] array , int x , int y){
        int tmp = array[x] ;
        array[x] = array[y] ;
        array[y] = tmp ;
    }
    public static void quickSort(int[] array){
        quick(array , 0 , array.length-1);
    }
    private static int partitionHoare(int[] array , int left , int right){
        int key = array[left] ;
        int tmp = left ;
        while(left < right){
            while (left < right && key <= array[right]){
                right -- ;
            }
            while (left < right && key >= array[left]){
                left ++ ;
            }
            swap(array , left , right);
        }
        swap(array , tmp , left);
        return left ;
    }
    private static void quick(int[] array , int start , int end){
        if(start >= end) return ;
        //三数取中
         int index = midOfThree(array , start , end);
         //获得中间位置后交换key 和 中间数字
         swap(array , index , start);

        int pivot = partitionHoare(array , start , end);
        quick(array , start , pivot-1);
        quick(array , pivot+1 , end);


    }
     //三数取中方法
    private static int midOfThree(int[] array, int left, int right) {
        int mid  = (left + right) / 2 ;
        if(array[left] < array[right]){
            if(array[mid] < array[left]){
                return left ;
            }else if(array[mid] > array[right]){
                return right ;
            }else{
                return mid ;
            }
        }else{
            if(array[mid] > array[left]){
                return left ;
            }else if(array[mid] < array[right]){
                return right ;
            }else{
                return mid ;
            }
        }


    }


}
